﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace expression_evaluation
{
    internal class Program
    {
        static void Main(string[] args)
        {
            var t = ToMidExpression("(-5-5) * (-3-2)");
            //foreach (var item in t)
            //{
            //    Console.Write(item + " ");
            //}

            var suffix = MidToSuffixExpression(t);
            foreach (var item in suffix)
            {
                Console.Write(item + " ");
            }

            int res = Calculate(suffix);
            Console.WriteLine($"\n结果：{res}");

            Console.ReadKey();
        }

        static List<string> ToMidExpression(string exprStr)
        {
            List<string> result = new List<string>();
            //遍历字符串
            for (int i = 0; i < exprStr.Length; i++)
            {
                //如果是括号，加入到列表
                if (exprStr[i]== '(' || exprStr[i] == ')')
                {
                    result.Add(exprStr[i].ToString());
                    continue;
                }
                //如果是操作符，加入到列表
                if (exprStr[i] == '+' || exprStr[i] == '-' || exprStr[i] == '*' || exprStr[i] == '/')
                {
                    result.Add(exprStr[i].ToString());
                    continue;
                }
                //如果是数字，加入到列表
                if (exprStr[i] >= '0' && exprStr[i] <= '9')
                {
                    //可能数字是多于一位的，因此进行拼接
                    string num = "";
                    while (i < exprStr.Length && exprStr[i] >= '0' && exprStr[i] <= '9')
                    {
                        num += exprStr[i].ToString();
                        i++;
                    }
                    result.Add(num); 
                    i--;
                }
            }

            return result;
        }

        static List<string> MidToSuffixExpression(List<string> midExpr)
        {
            List<string> result = new List<string>();
            Stack<string> st = new Stack<string>();

            for (int i = 0; i < midExpr.Count; i++)
            {
                //如果遇到的是数字，直接放入列表
                int tNum;
                if (int.TryParse(midExpr[i],out tNum))
                {
                    result.Add(midExpr[i]);
                    continue;
                }
                //如果遇到的是左括号，直接入栈
                if (midExpr[i] == "(")
                {
                    st.Push(midExpr[i]);
                    continue;
                }
                //如果遇到的是右括号，不停地将元素出栈并放入列表中，直到出栈元素是左括号
                if (midExpr[i] == ")")
                {
                    while (st.Peek() != "(")
                    {
                        result.Add(st.Pop());
                    }
                    st.Pop();
                    continue;
                }
                //如果是操作符，则需要比较当前操作符和栈顶元素的操作符的优先级
                if (midExpr[i] == "+" || midExpr[i] == "-" || midExpr[i] == "*" || midExpr[i] == "/")
                {
                    //对一元运算符"-"的特殊处理
                    if (midExpr[i] == "-")
                    {
                        //负号的特征是在表达式开头或者负号前一位字符为左括号，根据该特征进行判定
                        if (i == 0 || midExpr[i - 1] == "(")
                        {
                            //如果开头为-，则后一位一定是数字，将数字与负号结合并添加到列表
                            result.Add("-" + midExpr[++i]);
                            continue;
                        }
                    }

                    //当栈为空或者当前操作符的优先级比栈顶操作符的优先级高时，入栈
                    if (st.Count == 0 || Priority.GetPriority(midExpr[i][0]) > Priority.GetPriority(st.Peek()[0]))
                    {
                        st.Push(midExpr[i]);
                        continue;
                    }
                    result.Add(st.Pop());
                    st.Push(midExpr[i]);
                }
            }
            //遍历完后栈中可能还存留多个操作符，将其取出放入列表
            while (st.Count > 0)
            {
                result.Add(st.Pop());
            }

            return result;
        }

        static int Calculate(List<string> suffixExpr)
        {
            Stack<int> st = new Stack<int>();

            for (int i = 0; i < suffixExpr.Count; i++)
            {
                //如果是数字，将数字入栈
                int num;
                if (int.TryParse(suffixExpr[i],out num))
                {
                    st.Push(num);
                    continue;
                }
                //如果是操作符，将两个数组出栈，进行操作符的运算，将运算结果入栈
                int num1 = st.Pop();
                int num2 = st.Pop();
                int res = 0;
                if (suffixExpr[i] == "+")
                {
                    res = num2 + num1;
                }
                else if (suffixExpr[i] == "-")
                {
                    res = num2 - num1;
                }
                else if (suffixExpr[i] == "*")
                {
                    res = num2 * num1;
                }
                else if (suffixExpr[i] == "/")
                {
                    res = (int)(num2 * 1.0 / num1);
                }

                st.Push(res);
            }

            return st.Pop();
        }
    }
}
